package com.mdnote.practice.bit;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/17
 * @description 52. N皇后 II
 */
public class LeetCode52 {

    public int totalNQueens(int n) {

        return _totalQueen(n, 0, 0, 0, 0);
    }

    /**
     * N 皇后问题
     * @param n 皇后数量
     * @param row 第几行
     * @param column 存储可以防止皇后的位置 1表示不可以存放 0表示可以存放
     * @param pie 斜线位置信息
     * @param na 斜线位置信息
     * @return
     */
    private int _totalQueen(int n, int row, int column, int pie, int na) {

        // Terminator
        if (row == n) {
            // 存在一种走法
            return 1;
        }
        // Process
        int count = 0;
        // 需要知道我现在可以防止皇后的位置，1表示可以房的位置
        int availablePosition = ((1 << n) -1) & (~(column | pie | na));
        while (availablePosition != 0) {
            // -availablePosition 为逆元，需要注意思考有没有可能 = TMin TMin也是成立的
            // 0010 & 1110 = 0010
            int position = availablePosition & (-availablePosition);
            // 防止皇后，下面是将最后一个1设置为0
            availablePosition = (availablePosition - 1) & availablePosition;

            // Drill down
            count += _totalQueen(n, row + 1, column | position, (pie | position) << 1, (na | position) >> 1);
            // Restore current data  因为传递ad是拷贝，所以不用回复
        }
        return count;
    }
}
